home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
PsL Monthly 1994 December
/
PSL Monthly Shareware CD-ROM (Public Software Library)(December 1994).bin
/
prgmming
/
dos
/
c3
/
kwiksort.c
< prev
next >
Wrap
C/C++ Source or Header
|
1992-10-17
|
5KB
|
237 lines
/*
An animated quick sort program. Based on the recursive Quicksort
algorithm in "Algorithms + Data Structures = Programs" by Niklaus Wirth,
Prentice-Hall, Inc., 1976, ISBN 0-13-022418-9. See chapter 2, section
2.2.6.
Note that there are better ways of actually implementing the Quicksort
algorithm.
If you have a version of the compiler prior to TC++, you'll need to
replace the calls to _setcursortype() with something else (or nothing).
Released to the public domain by the author.
Gary M. Blaine CIS 70007,4659
*/
#include <stdlib.h>
#include <conio.h>
#include <time.h>
#include <bios.h>
#include <dos.h>
/* function prototypes */
void Quicksort(char* letters, int left, int right);
void inc(int* n);
void dec(int* n);
void display(char* letters, int i, int j);
void init_arrows(int i, int j);
void swap(char* letters, int i, int j);
#define SIZE 40
int main(void)
{
char letters[SIZE];
int i;
randomize();
_setcursortype(_NOCURSOR);
clrscr();
for(i = 0; i < SIZE; i++) /* initialize the array */
letters[i] = random(26) + 'A';
display(letters, 0, SIZE-1); /* display the array */
Quicksort(letters, 0, SIZE-1); /* sort the array */
gotoxy(1, 3);
_setcursortype(_NORMALCURSOR);
return 0;
}
/* sort an array of letters */
void Quicksort(char* letters, int left, int right)
{
int i, j;
char x;
/* display initial left and right pointers */
init_arrows(left, right);
i = left;
j = right;
x = letters[(left+right) / 2];
/* do the partition */
do
{
while(letters[i] < x) inc(&i);
while(letters[j] > x) dec(&j);
if(i <= j)
{
swap(letters, i, j);
inc(&i);
dec(&j);
}
}
while(i <= j);
/* sort left partition */
if(left < j)
Quicksort(letters, left, j);
/* sort right partition */
if(i < right)
Quicksort(letters, i, right);
/* clear away the little arrow pointers */
gotoxy(1, 1);
clreol();
}
/* increment a variable and update arrow position */
void inc(int* n)
{
int row = 1;
int col = *n * 2 + 1;
gotoxy(col, row); /* get rid of little arrow */
putch(' ');
(*n)++; /* increment the variable in calling function */
col = *n * 2 + 1; /* display the new arrow location */
gotoxy(col, row);
putch(0x19); /* a down pointing arrow */
delay(100);
}
/* decrement a variable and update arrow position */
void dec(int* n)
{
int row = 1;
int col = *n * 2 + 1;
gotoxy(col, row); /* get rid of little arrow */
putch(' ');
(*n)--; /* decrement the variable in calling function */
col = *n * 2 + 1; /* display the new arrow location */
gotoxy(col, row);
putch(0x19); /* a down pointing arrow */
delay(100);
}
/* display the array */
void display(char* letters, int i, int j)
{
int n;
int row = 1 + 1;
for(n=i; n<=j; n++)
{
gotoxy(n*2+1, row);
putch(letters[n]);
}
}
/* swap array elements */
void swap(char* letters, int i, int j)
{
int row = 2;
int rowi = 3;
int rowj = 4;
int mi, mj;
char ci = letters[i]; /* remember the characters at i, j */
char cj = letters[j];
char tmp = letters[i]; /* swap array elements */
letters[i] = letters[j];
letters[j] = tmp;
/* move ith character down */
for(mi = row; mi < rowi; mi++)
{
gotoxy(i*2+1, mi);
putch(' ');
gotoxy(i*2+1, mi+1);
putch(ci);
delay(100);
}
/* move jth character down */
for(mj = row; mj < rowj; mj++)
{
gotoxy(j*2+1, mj);
putch(' ');
gotoxy(j*2+1, mj+1);
putch(cj);
delay(100);
}
/* move characters horizontally */
for(mi=i*2+1, mj=j*2+1; mi<j*2+1; mi++, mj--)
{
gotoxy(mi, rowi);
putch(' ');
gotoxy(mj, rowj);
putch(' ');
gotoxy(mi+1, rowi);
putch(ci);
gotoxy(mj-1, rowj);
putch(cj);
delay(20);
}
/* move ith character back up into jth position */
for(mi = rowi; mi > row; mi--)
{
gotoxy(j*2+1, mi);
putch(' ');
gotoxy(j*2+1, mi-1);
putch(ci);
delay(100);
}
/* move jth character back up into ith position */
for(mj = rowj; mj > row; mj--)
{
gotoxy(i*2+1, mj);
putch(' ');
gotoxy(i*2+1, mj-1);
putch(cj);
delay(100);
}
/* let the user quit by hitting any key */
if( bioskey(1) )
{
bioskey(0);
gotoxy(1, 3);
cputs("User terminated");
_setcursortype(_NORMALCURSOR);
exit(1);
}
}
/* display the little arrow pointers */
void init_arrows(int i, int j)
{
gotoxy(1, 1); /* get rid of any existing arrows */
clreol();
gotoxy(i*2+1, 1);
putch(0x19); /* a down pointing arrow */
gotoxy(j*2+1, 1);
putch(0x19); /* a down pointing arrow */
}